package com.demo.java.OD401_450.OD430;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【地图寻宝(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146320710
 */
public class OdMain {
    static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};  // 四个方向的移动
    static int ans = 0;  // 用于记录可以访问的合法位置数量

    // 计算数字的各位之和
    public static int cal_digit_sum(int n) {
        int ans = 0;
        while (n != 0) {
            ans += n % 10;  // 取个位数字
            n /= 10;  // 去掉个位
        }
        return ans;
    }

    // 深度优先搜索
    public static void dfs(int i, int j, int m, int n, int k, int[][] checklist, int[][] grid) {
        checklist[i][j] = 1;  // 标记当前位置已访问
        ans += 1;  // 访问合法位置，增加计数
        for (int[] dir : DIRECTIONS) {  // 遍历四个方向
            int ni = i + dir[0];  // 计算新位置的行坐标
            int nj = j + dir[1];  // 计算新位置的列坐标
            // 检查新位置是否合法
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && checklist[ni][nj] == 0 && grid[ni][nj] <= k) {
                dfs(ni, nj, m, n, k, checklist, grid);  // 递归访问新位置
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();  // 读取行数
        int n = scanner.nextInt();  // 读取列数
        int k = scanner.nextInt();  // 读取最大数位和

        int[][] grid = new int[m][n];  // 创建网格
        int[][] checklist = new int[m][n];  // 创建检查表，用于标记是否访问过

        // 填充网格，每个位置的值为其坐标数位和
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j);  // 计算数位和
            }
        }

        // 从起点 (0, 0) 开始进行深度优先搜索
        dfs(0, 0, m, n, k, checklist, grid);
        System.out.println(ans);  // 输出可以访问的位置数量
    }
}
